package cn.bellychang.wangzheng.graph;

import java.util.LinkedList;
import java.util.Queue;

/**
 *
 * 无向图
 *
 * @author ChangLiang
 * @date 2021/2/11
 */
public class Graph {

    /**
     * 顶点的个数 vertex
     */
    private int v;

    /**
     * 需要先把a、f、e等对象转化成1、2、3....这样的编号 邻接表
     */
    private LinkedList<Integer>[] adj;

    public Graph(int v) {
        this.v = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList<>();
        }
    }

    /**
     *
     * @param s 起始顶点
     * @param t 终止顶点
     */
    public void addEdge(int s, int t) {
        adj[s].add(t);
        adj[t].add(s);
    }


    /**
     * 全局变量或类成员变量
     *
     * 当我们已经找到终止顶点 t 之后，我们就不再递归地继续查找了
     */
    boolean found = false;

    /**
     *
     * @param s 起始顶点
     * @param t 终止顶点
     */
    public void dfs(int s, int t) {

        found = false;

        // 深度优先搜索代码实现也用到了visited 变量
        boolean[] visited = new boolean[v];

        // 深度优先搜索代码实现也用到了 prev 变量
        int[] prev = new int[v];
        for (int i = 0; i < v; i++) {
            prev[i] = -1;
        }
        recurDfs(s,t,visited,prev);
        print(prev, s, t);
    }

    /**
     *
     * @param w
     * @param t 终止顶点 出口
     * @param visited
     * @param prev
     */
    private void recurDfs(int w, int t, boolean[] visited, int[] prev) {
        // 递归终止条件
        if (found == true) {
            return;
        }
        visited[w] = true;
        if (w == t) {
            found = true;
            return;
        }
        for (int i = 0; i < adj[w].size(); i++) {
            int q = adj[w].get(i);
            if (!visited[q]) {
                prev[q] = w;
                recurDfs(q,t,visited,prev);
            }
        }
    }

    /**
     *
     * 搜索一条从 s 到 t 的路径
     * 实际上，这样求得的路径就是从 s 到 t 的最短路径
     *
     * @param s 起始顶点
     * @param t 终止顶点
     */
    public void bfs(int s, int t) {

        if (s == t) {
            return;
        }
        // visited是用来记录已经被访问的顶点，用来避免顶点被重复访问。
        // 如果顶点 q 被访问，那相应的 visited[q] 会被设置为 true。
        boolean[] visited = new boolean[v];

        visited[s] = true;

        // queue是一个队列，用来存储已经被访问、但相连的顶点还没有被访问的顶点。
        // 因为广度优先搜索是逐层访问的，也就是说，我们只有把第 k 层的顶点都访问完成之后，才能访问第 k+1 层的顶点。
        // 当我们访问到第 k 层的顶点的时候，我们需要把第 k 层的顶点记录下来，稍后才能通过第 k 层的顶点来找第 k+1 层的顶点。
        // 所以，我们用这个队列来实现记录的功能。
        Queue<Integer> queue = new LinkedList<>();
        queue.add(s);

        // prev用来记录搜索路径。当我们从顶点 s 开始，广度优先搜索到顶点 t 后，prev 数组中存储的就是搜索的路径。
        // 不过，这个路径是反向存储的。prev[w] 存储的是，顶点 w 是从哪个前驱顶点遍历过来的。
        // 比如，我们通过顶点 0 的邻接表访问到顶点 1，那 prev[1] 就等于 0。
        // 为了正向打印出路径，我们需要递归地来打印，你可以看下 print() 函数的实现方式。
        int[] prev = new int[v];
        for (int i = 0; i < v; i++) {
            prev[i] = -1;
        }

        while (queue.size() != 0) {
            int w = queue.poll();
            for (int i = 0; i < adj[w].size(); i++) {
                int q = adj[w].get(i);
                if (!visited[q]) {
                    prev[q] = w;
                    if (q == t) {
                        print(prev, s, t);
                        return;
                    }
                    visited[q] = true;
                    queue.add(q);
                }
            }
        }
    }

    /**
     * 递归打印 s-->t 的路径
     * @param prev
     * @param s
     * @param t
     */
    private void print(int[] prev, int s, int t) {

        if (prev[t] != -1 && t != s) {
            print(prev, s, prev[t]);
        }
        System.out.print(t + " ");
    }
}
